CF1934 D2. XOR Break — Game Version题解

D2. XOR Break — Game Version

题目翻译

​ 题目给我们一个初始数字n，我们要和对手进行博弈，我们可以选择先后手，我们与对手进行的游戏是这样的，当前数字初始为p，当前回合的选手需要构造两个数字p1，p2，满足（0 < p1 < p, 0 < p2 < p, p1 ^ p2 == p)，若无法构造出p1，p2则当前回合玩家输，然后另一个人挑选其中任意一个数作为当前数字p，并开始它的回合。我们最多可以进行63次回合，需要保证必胜。初始数字n < 1e18。交互题，系统给出对面的操作。

思路

​ 首先我们可以发现一个关键的边界条件，当初始数字中为1的位为1时我们无法对其进行拆解，此时是必败态。我们考虑如何让对手到达这个状态或是这个状态由和转移过来。一个简单的必胜态是有两位数的情况，此时我们拆成两个1位为1的位的数则必胜。继续推广我们发现通过构造所有的为1的位为偶数时都是必胜态，奇数都是必败态，具体证明如下，对于一个偶数个位为1的数我们一定可以把其拆成两个为1的位为奇数的数，而对于为1的位为偶数的数我们无论怎么拆都是一奇数位为1，一个偶数位为1，所以我们只要继续挑选那个偶数位1的数进行拆分就可继续必胜。具体的拆分为了减少对面新增的1的位，我们直接把最高位1拆走，剩余的构成另外一个数即可，在题目要求下易证操作回合小于等于63。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int getcnt(ll x){
    int ans = 0;
    for(int i = 0; i < 63; i++){
        if((x >> i) & 1)
            ans += 1;
    }
    return ans;
}

void solve(){
    ll n;
    std::cin >> n;
    int cnt = getcnt(n);
    ll p1 = n;
    ll p2 = n;
    if(cnt % 2 == 1){
        std::cout << "second" << std::endl;
        std::cin >> p1 >> p2;
    }
    else{
        std::cout << "first" << std::endl;
    }

    int op = 0;
    while(true){
        if(p1 == 0 && p2 == 0)
            break;
        op += 1;
        if(getcnt(p1) % 2 != 0)
            std::swap(p1, p2);
        ll out1 = (1LL << std::__lg(p1));
        ll out2 = (p1 ^ out1);

        std::cout << out1 << space << out2 << std::endl;
        std::cin >> p1 >> p2;
    }
}